package leetcode每日一题;

import java.util.*;

/**
 * 1. 问题描述
 *      给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串
 *
 * 2. 算法分析
 *      1. 题目分析：
 *          异位词指的是：字符组成相同，但是顺序不同的字符串，给定一个字符串的数组，我们将
 *          异位词放置到一个List<String>容器中，最终将这些分类之后的list容器放置在list
 *          集合中返回即可
 *      2. 算法分析：
 *          1. 我们如何判断两个字符串是否为异位字符串?
 *
 *
 *          2.
 * 3. 代码实现
 *
 */
@SuppressWarnings("all")
public class 字母异位词分组 {
    public static void main(String[] args) {
        System.out.println(isAnagrams3("", ""));
    }

    // 将字符串转化为char型数组 + 数组排序 + 线性比较   时间复杂度和空间复杂度都比较高
    // 时间复杂度为 O(n + 2nlogn)  空间复杂度为 O(2n)
    public static boolean isAnagrams1(String s1,String s2) {
        if(s1.length() != s2.length()) {return false;}
        char[] char1 = s1.toCharArray();
        char[] char2 = s2.toCharArray();
        Arrays.sort(char1); Arrays.sort(char2);
        for(int i = 0; i < s1.length(); i++) {
            if(char1[i] != char2[i]) {
                return false;
            }
        }
        return true;
    }

    // 采用hash法
    // 时间复杂度为 O(n + 2n)  空间复杂度为 O(52)
    public static boolean isAnagrams2(String s1,String s2) {
        if (s1.length() != s2.length()) {return false;}
        int[] temp1 = new int[26];
        int[] temp2 = new int[26];
        for (int i = 0; i < s1.length(); i++) {
            temp1[s1.charAt(i) - 'a']++;
            temp2[s2.charAt(i) - 'a']++;
        }
        for (int i = 0; i < s1.length(); i++) {
            if (temp1[i] != temp2[i]) {
                return false;
            }
        }
        return true;
    }

    // hash法的优化  只是用一个辅助数组
    // 时间O(2n)   空间O(26)
    public static boolean isAnagrams3(String s1,String s2) {
        if (s1.length() != s2.length()) {return false;}
        int[] temp = new int[26];
        for (int i = 0; i < s1.length(); i++) {
            temp[s1.charAt(i)-'a']++;
            temp[s2.charAt(i)-'a']--;
        }
        for (int item : temp) {
            if (item != 0) {
                return false;
            }
        }
        return true;
    }

    // hash法 对上述3的改进
    public static boolean isAnagrams4(String s,String t) {
        if(s.length() != t.length()) return false;
        int[] s1 = new int[26];
        for(char c : s.toCharArray()){
            s1[c-'a']++;
        }
        for(char c: t.toCharArray()){
            s1[c-'a']--;
        }
        for(int num : s1){
            if(num!=0){
                return false;
            }
        }
        return true;
    }

    /**
     * 正确代码
     * @param strs
     * @return
     */
    public static List<List<String>> groupAnagrams1(String[] strs) {
        Map<String, List<String>> map = new HashMap<String, List<String>>();
        for (String str : strs) {
            char[] array = str.toCharArray(); // 将字符串转化为字符数组
            Arrays.sort(array); // 排序
            String key = new String(array); // 将排序之后的数组转化为字符串作为key
            // getOrDefault方法的含义：
            // 如果当前key存在，就返回当前key对象的value,否则返回默认值即第二个参数
            // 下面的代码的含义：
            // 当前key已经存在，获取当前key对应的list，之后将当前的s添加到list中
            // 如果当前key不存在，创建一个新的list，并添加到list中
            List<String> list = map.getOrDefault(key, new ArrayList<String>());
            list.add(str);
            map.put(key, list);
        }
        return new ArrayList<List<String>>(map.values());
    }

    /**
     * 错误代码
     */
    /**
     * 下述代码有逻辑问题：对于位运算而言此题无法判断两个字符串是否为异位置字符串
     *  例如：aaab bbba，无论哪一种位运算，最终结果都是一样的，但是这两个显然不
     *  是异位置字符串
     *
     *  此外leetcode平台的一个小坑：在idea中判断""可以使用 = 或者 !=,但是在
     *  leetcode中只能使用equals()方法判断，否则会报错
     * @param strs
     * @return
     */
    public static List<List<String>> groupAnagrams2(String[] strs) {
        List<List<String>> ans = new ArrayList<>(); //  存放最终的结果
        Map<Integer,List<String>> map = new HashMap<>(); // key：字符串对应字符的位运算结果，List<String>存放位运算相同的字符串
        for(String s : strs) { // 线性扫描strs
            // 判断当前元素是否为空字符串
            if(s != "") {
                int temp = s.charAt(0); // 记录当前字符串的位运算结果
                for(int j = 1; j < s.length(); j++) {
                    temp ^= s.charAt(j);
                }
                if(map.containsKey(temp)) { // 判断当前位运算结果是否在map的key中出现
                    // 如果出现
                    map.get(temp).add(s); // 将当前s添加到对应的value：list集合中
                } else{
                    // 如果没有出现
                    List<String> list = new ArrayList<>(); list.add(s);
                    map.put(temp,list);
                }
            } else {
                // 当前s为""
                List<String> list = new ArrayList<>(); list.add(s);
                map.put(-1,list);
            }
        }
        // 扫描map
        for(int key : map.keySet()) {
            ans.add(map.get(key));
        }
        return ans;
    }
}
